Subject: Re: Data structure for a Text Editor
From: [email-masked] (Colin Plumb)
Date: Wed, 13 Apr 94 10:24:52 GMT
Newsgroups: comp.programming

In article <[email-masked]>,
Douglas Squirrel <[email-masked]> wrote:
>I am writing a text editor on the Macintosh in Think C.
>The text is likely to be large (often over 400K, peak about 800K).
>Editing will be minimal, but viewing will be the main use.  That is, editing
>should be quick, but viewing should be quicker, even at the expense of edit 
>speed.
>Memory will not be a big concern (but it would be nice to avoid being a hog).
>
>I am using a linked list of lines terminated by newlines.  The linked list
>will actually be a balanced binary tree as described by Knuth vol. 3 p.452 ff.
>
>Is this 1) reasonable and 2) fast?

I generally hate the linked-list-of-lines technique.
For lots of good ideas, see The Craft of Text Editing, by Craig Finseth.

Probably the nest is the paged buffer gap.  You break the text into
a series of pages, each of which is managed by a buffer-gap system.
You can read the text in a page at a time and build the tree as you do it.
If you don't edit, the text is basically contiguous in memory.  If you
edit it, only the pages that hold the data are disturbed.  Using
fixed-size pages improves memory fragmentation considerably.

What I'd do is in the extra info per page, store the number of newlines
in the page.  Then use the standard technique in the tree of
marking each node with the number of newlines in its left subtree
to let you find the page that holds a given newline (the start of a
given line) quickly, followed by which linear search is fine in
a finite-sized page.  That lets you find a given line number very
quickly.

If you do line-wrapping, and the display width is constant, you can do the
same for visible lines.  Count a newline every time you have a hard newline
or reach 80 characters (or whatever).  It sort of breaks down if the
window keeps changing size, though.  To scroll backwards, you'll have to find
the previous line's start and work forward from there to figure out where the
visible tail of it starts.

Don't forget to look at a variety of balanced trees.  I like red-black trees,
myself.  Then there are B-tree-like variants.
-- 
	-Colin